#include "String.h"
void InitString(String *s)
{
    s->array_ = (DataType *)malloc(sizeof(DataType));
    s->array_[0] = '\0';
    s->capacity_ = s->size_ = 0;
}
void reserve(String *s, int n)
{
    if (n < s->capacity_)
        return;
    DataType *tmp = (DataType *)malloc(sizeof(DataType) * n + 1);
    for (int i = 0; i < s->size_; i++)
    {
        tmp[i] = s->array_[i];
    }
    for (int i = s->size_; i <= n; i++)
    {
        tmp[i] = '\0';
    }
    free(s->array_);
    s->array_ = tmp;
    s->capacity_ = n;
}
bool StrAssign(String *s, char chars[])
{
    int len = strlen(chars);
    if (s->size_ + len > s->capacity_)
    {
        reserve(s, s->size_ + len);
    }
    for (int i = 0; i <= len; i++)
    {
        s->array_[s->size_ + i] = chars[i];
    }
    s->size_ = s->size_ + len;
    return true;
}
bool StrCopy(String *s, String copy)
{
    if (s->capacity_ < copy.size_)
    {
        reserve(s, copy.size_);
    }
    for (int i = 0; i < copy.size_; i++)
    {
        s->array_[i] = copy.array_[i];
    }
    s->size_ = copy.size_;
    return true;
}
bool StrEmpty(String *s)
{
    return s->size_ == 0;
}
int StrCompare(String *s, String *tmp)
{
    // int n1 = s->size_;
    // int n2 = tmp->size_;
    // int i = 0;
    // while (i < n1 && i < n2)
    // {
    //     if (s->array_[i] > tmp->array_[i])
    //         return 1;
    //     else if (s->array_[i] < tmp->array_[i])
    //         return -1;
    //     else
    //         i++;
    // }
    // if (n1 == n2)
    //     return 0;
    // if (i == n1)
    //     return -1;
    // if (i == n2)
    //     return 1;
    for (int i = 1; i <= s->size_ && i < tmp->size_; i++)
    {
        if (s->array_[i] != tmp->array_[i])
        {
            return s->array_[i] - tmp->array_[i];
        }
    }
    return s->size_ - tmp->size_;
}
int StrLength(String *s)
{
    return s->size_;
}
bool SubString(String *s, String *ret, int pos, int len)
{
    // reserve(ret, len);
    // if (pos + len - 1 >= s->size_)
    //     return false;
    // for (int i = 0; i < len; i++)
    // {
    //     ret->array_[i] = s->array_[pos - 1 + i];
    // }
    // ret->array_[len] = '\0';
    // ret->size_ = len;
    // return true;
    if (pos + len - 1 > s->size_)
        return false;
    for (int i = 1; i <= len; i++)
    {
        ret->array_[i] = s->array_[i + pos - 1];
    }
    ret->size_ = len;
    return true;
}
bool Concat(String *s, String *tmp, String *ret)
{
    reserve(ret, s->size_ + tmp->size_);
    for (int i = 0; i < s->size_; i++)
    {
        ret->array_[i] = s->array_[i];
    }
    for (int i = 0; i < tmp->size_; i++)
    {
        ret->array_[s->size_ + i] = tmp->array_[i];
    }
    ret->size_ = s->size_ + tmp->size_;
    return true;
}
void ClearString(String *s)
{
    s->size_ = 0;
}
void DestroyString(String *s)
{
    free(s->array_);
    s->array_ = NULL;
    s->capacity_ = s->size_ = 0;
}

// int Index(String *s, String *tmp)
// {
//     int i = 1;
//     int n = s->size_;
//     int m = tmp->size_;
//     String ret;
//     InitString(&ret);
//     reserve(&ret, m);
//     while (i <= n - m + 1)
//     {
//         SubString(s, &ret, i, m);
//         if (StrCompare(tmp, &ret) != 0)
//             i++;
//         else
//             return i;
//     }
//     return 0;
// }

int Index(String *s, String *tmp)
{
    int n = s->size_, m = tmp->size_;
    int i = 1, j = 1;
    while (j <= m && i <= n)
    {
        if (s->array_[i] == tmp->array_[i])
        {
            i++;
            j++;
        }
        else
        {
            i = i - j + 2;
            j = 1;
        }
    }
    if (j > m)
    {
        // return i - m;
        return i - j + 1;
    }
    return 0;
}

// c++
//  void getNext(const string &pattern, vector<int> &next)
//  {
//      int m = pattern.length();
//      next.resize(m);
//      next = -1;
//      int k = -1;
//      for (int i = 1; i < m; i++)
//      {
//          while (k >= 0 && pattern[i] != pattern[k])
//          {
//              k = next[k];
//          }
//          if (pattern[i] == pattern[k])
//          {
//              k++;
//          }
//          next[i] = k;
//      }
//  }

// int KMPSearch(const string &text, const string &pattern)
// {
//     vector<int> next;
//     getNext(pattern, next);
//     int n = text.length();
//     int m = pattern.length();
//     int i = 0; // text的指针位置
//     int j = 0; // pattern的指针位置
//     while (i < n)
//     {
//         if (text[i] == pattern[j])
//         {
//             if (j == m - 1)
//             {
//                 return i - m + 1;
//             }
//             else
//             {
//                 i++;
//                 j++;
//             }
//         }
//         else if (j > 0)
//         {
//             j = next[j];
//         }
//         else
//         {
//             i++;
//         }
//     }
// }

// next数组
String *makeNext(String *t)
{
}

//
int KMP(String *s, String *t)
{
    int i = 1, j = 1;
    String *next = makeNext(t);
    while (j <= t->size_ && i <= s->size_)
    {
        if (j == 0 || s->array_[i] == t->array_[j])
        {
            i++;
            j++;
        }
        else
        {
            j = next->array_[j];
        }
    }
    if (j > t->size_)
    {
        return i - t->size_;
    }
    return 0;
}

// nextval数组

String *makeNextval(String *next, String *t)
{
    int j = 2;
    String *nextval = (String *)malloc(sizeof(String));
    InitString(nextval);
    nextval->array_[0] = -1;
    nextval->array_[1] = 0;
    while (j <= t->size_)
    {
        if (t->array_[j] == t->array_[next->array_[j]])
        {
            nextval->array_[j] = nextval->array_[next->array_[j]];
        }
        else
        {
            nextval->array_[j] = next->array_[j];
        }
        j++;
    }
    return nextval;
}